package cn.zifangsky.linkedlist.questions;

import org.junit.Test;

import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;

/**
 * 如何逐对逆置单向链表？
 * @author zifangsky
 *
 */
public class Problem_007_PairwiseReverseList {
	
	/**
	 * @时间复杂度 O(n)
	 * @param headNode
	 * @return
	 */
	public SinglyNode ReverseList(SinglyNode headNode){
		SinglyNode tempNode=null;
		
		if(headNode == null || headNode.getNext() == null){
			return headNode;
		}else{
			tempNode = headNode.getNext();
			headNode.setNext(tempNode.getNext());
			tempNode.setNext(headNode);
			tempNode.getNext().setNext(ReverseList(headNode.getNext()));
			
			return tempNode;
		}
	}
	
	@Test
	public void testMethods(){
		SinglyNode headNode = new SinglyNode(11);
		
		SinglyNode currentNode = headNode;
		for(int i=2;i<=7;i++){
			SinglyNode tmpNode = new SinglyNode(11 * i);
			currentNode.setNext(tmpNode);
			currentNode = tmpNode;
		}
		
		//遍历初始链表
		SinglyNodeOperations.print(headNode);

		headNode = ReverseList(headNode);
		
		//遍历最终结果
		SinglyNodeOperations.print(headNode);

	}
	
}
